#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX;
int n;

int main(int argc, char const *argv[])
{
    freopen("prim.txt", "r", stdin);

    cin >> n;

    int graph[n + 1][n + 1];
    int t;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> t;
            graph[i][j] = t == 0 ? INF : t;
        }
    }

    // for(int i = 1; i <= n; ++i){
    //     for(int j = 1; j <= n; ++j){
    //         cout << graph[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    int startid = 1;
    int S[n + 1]; S[startid] = 0;   // 已加入最小生成树的节点
    int U[n + 1];                   // 未加入节点
    for(int i = 1; i <= n; ++i)
        U[i] = graph[startid][i];
    bool flag[n + 1] = {false}; flag[startid] = true;

    for(int i = 2; i <= n; ++i){
        // update S
        int minid, mindis = INF;
        for(int j = 1; j <= n; ++j){
            if(!flag[j] && U[j] < mindis){
                minid = j;
                mindis = U[j];
            }
        }
        S[minid] = mindis;
        flag[minid] = true;
        cout << minid << " " << mindis << endl;
        
        // update U
        for(int j = 1; j <= n; ++j){
            if(!flag[j] && graph[minid][j] < U[j])
                U[j] = graph[minid][j];
        }
    }

    return 0;
}
